package com.yue.sort;

import java.util.Arrays;

/**
 * Created by qiuyang on 2017/9/7.
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arr = {1, 4, 2, 1, 5, 7, 10, 2, 5, 8, 9};
//        int[] arr = {1, 2, 3, 4, 5, 6};
//        int[] arr = {6, 5, 4, 3, 2, 1};
//        int[] arr = {};
        print(arr);
        print(new int[0]);
//        sort(arr);
//        binarySort(arr);
        shellSort(arr, 5);
    }

    public static void print(int arr[]) {
        for (int i : arr) {
            System.out.print(i + "  ");
        }
        System.out.println();
    }

    public static int[] sort(int[] arr) {
        if (arr == null) {
            return null;
        }

        if (arr.length == 0) {
            return new int[0];
        }

        int[] result = Arrays.copyOf(arr, arr.length);
        int temp = 0;
        for (int i = 1; i < result.length; i++) {
            for (int j = i; j > 0; j--) {
                if (result[j] < result[j - 1]) {
                    temp = result[j];
                    result[j] = result[j - 1];
                    result[j - 1] = temp;
                    print(result);
                } else {
                    print(result);
                    break;
                }
            }
        }
        return result;
    }

    public static int[] binarySort(int[] arr) {
        if (arr == null) {
            return null;
        }

        if (arr.length == 0) {
            return new int[0];
        }

        int[] result = Arrays.copyOf(arr, arr.length);

        for (int i = 1; i < result.length; i++) {

            int left = 0;
            int right = i - 1;
            int mid = 0;
            int temp = result[i];
            while (left <= right) {
                mid = (left + right) / 2;
                if (temp > result[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

            for (int j = i; j > left; j--) {
                result[j] = result[j - 1];
                print(result);
            }
            if (left != i) {
                result[left] = temp;
                print(result);
            }
        }

        return result;
    }

    public static int[] shellSort(int[] arr, int d) {
        if (arr == null) {
            return null;
        }

        if (arr.length == 0) {
            return new int[0];
        }

        if (d > arr.length) {
            d = arr.length;
        }

        int[] result = Arrays.copyOf(arr, arr.length);

        while (true) {
            d = d / 2;
            for (int i = 0; i < d; i++) {
                for (int j = i; j < result.length; j += d) {
                    int temp = 0;
                    for (int k = j; k >= d; k -= d) {
                        if (result[k] < result[k - d]) {
                            temp = result[k];
                            result[k] = result[k - d];
                            result[k - d] = temp;
                            print(result);
                        } else {
                            print(result);
                            break;
                        }
                    }
                }
            }
            if (d == 1) {
                break;
            }
        }
        return result;
    }
}
